//class Solution {
//public:
//    vector<vector<int>> ret;
//    vector<int> path;
//    int aim;
//    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//        aim = target;
//        dfs(candidates, 0, 0);
//        return ret;
//    }
//
//    void dfs(vector<int>& candidates, int prevSum, int pos)
//    {
//        if (prevSum == aim)
//        {
//            ret.push_back(path);
//            return;
//        }
//        if (prevSum > aim || pos >= candidates.size()) return;
//        for (int i = pos; i < candidates.size(); i++)
//        {
//            path.push_back(candidates[i]);
//            dfs(candidates, prevSum + candidates[i], i);
//            path.pop_back();
//        }
//    }
//};
//

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true;
        for (int j = 1; j <= n; j++)
            if (p[j] == '*') dp[0][j] = true;
            else break;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (p[j] == '?') dp[i][j] = dp[i - 1][j - 1];
                else if (p[j] == '*') dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                else dp[i][j] == (s[i] == p[j]) ? dp[i - 1][j - 1] : false;
            }
        }
        return dp[m][n];
    }
};